package com.jia.leetCode;

import java.util.Arrays;

public class Pro0016 {
    public int threeSumClosest(int[] nums, int target) {
        int res = nums[0] + nums[1] + nums[nums.length - 1];
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-2; i++) {
        	int start = i + 1, end = nums.length - 1;;
        	while(start < end) {
        		int sum = nums[i] + nums[start] + nums[end];
        		if(sum > target) {
        			end --;
        		}else {
        			++ start;
        		}
        		if(Math.abs(sum - target) < Math.abs(res - target)) {
        			res = sum;
        		}
        	}
        }
        return res;
    }

	public int threeSumClosest2(int[] num, int target) {
		int result = num[0] + num[1] + num[num.length - 1];
		Arrays.sort(num);
		for(int i = 0; i + 2 < num.length; i++) {
			int l = i+1, r = num.length - 1;
			while(l < r) {
				int sum = num[i]+num[l]+num[r];
				if(sum > target) {
					while(l < r && num[r] == num[r-1]) --r; //equal
					--r;
				}else if(sum < target) {
					while(l < r && num[l] == num[l+1]) ++l;//
					++l;
				}else {
					return target;
				}
				if(Math.abs(target - sum) < Math.abs(target - result)) {
					result = sum;
				}
			}
		}
		return result;
	}
}
